package study.datastructure.hashmap;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-01-26 21:00
 */

import study.datastructure.tree.TreeNode;

import java.util.*;

/**
 * 2025/1/26,
 */


public class s1 {

    public int[] twoSum(int[] nums, int target) {

        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();

        if (nums == null || nums.length == 0) {
            return result;
        }

        for (int i = 0; i < nums.length; i++) {
            int ti = target - nums[i];
            //找到
            if (map.containsKey(ti)) {
                result[0] = map.get(ti);
                result[1] = i;
                return result;
            } else {
                //没找到
                map.put(nums[i], i);
            }
        }
        return result;
    }

    /**
     * 最长连续子序列
     * <p>
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {

        //TreeSet set = new TreeSet();
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int longest = 0;
        for (int sn : set) {

            // 找到起始节点
            if (set.contains(sn - 1)) {
                continue;
            }

            int y = sn + 1;

            while (set.contains(y))
                y++;
            longest = Math.max((y - sn), longest);
        }

        return longest;

    }


    int res=0,k = 0;
    /**
     * 二叉树搜索树中第k小的元素
     *
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {

        if (root == null) {
            return;
        }
        dfs(root.left);

        if (--k == 0) {
            res = root.val;
            return;
        }
        dfs(root.right);
    }

    /**
     * 二叉搜索树的右视图
     *
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
    private void dfs(TreeNode root, int depth, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(root.val);
        }

        dfs(root.right, depth + 1, result);
        dfs(root.left,depth+1,result);

    }

}
